package com.example.algorithm.LinkedListAlgorithm;

/**
 * 两个有序链表合并为一个. 递归
 * 思路:
 * 合并两个有序序列，这个归并排序中的一个关键步骤。
 * 这里是要合并两个有序的单链表。由于链表的特殊性，在合并时只需要常量的空间复杂度。
 * @author ZMJ
 * @date 2020/3/23
 */
public class LinkedTwoOrderLinkedMergeOne {

    public static Node twoOrderLinkedMergeOne(Node l1, Node l2) {
        // 其中一个为空, 另一个为头, 都为空直接返回Null
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }

        // 合并
        Node pre = new Node("-1", "-1"); //新建一个头结点操作
        Node end = pre;//定义一个当前节点指向head头结点方便操作
        Node h1 = l1;
        Node h2 = l2;
        while (h1 != null && h2 != null) {
            if (Integer.valueOf(h1.getKey()) > Integer.valueOf(h2.getKey())) {
                end.setNext(h2); //这里，将待排序节点直接拼接在新节点后，而不用再创建新节点。节省了空间复杂度。
                h2 = h2.getNext();
            } else {
                end.setNext(h1);
                h1 = h1.getNext();
            }
            //记得加上这一句将链表前后连接起来！否则最后一顿操作后只剩最后一个结点！
            end = end.getNext();
        }

        if (h1 != null) {
            end.setNext(h1); // h1还有直接上链
        }
        if (h2 != null) {
            end.setNext(h2); // h2还有直接上链
        }
        // 链表头
        return pre.getNext();
    }


    public static void main(String[] args) {
        // 数组变成链表
        String[] arr1 = new String[]{"1", "5", "8"};
        Node head1 = Node.createLinkedListByArr(arr1);
        String[] arr2 = new String[]{"0", "4", "6", "10"};
        Node head2 = Node.createLinkedListByArr(arr2);

        Node head = twoOrderLinkedMergeOne(head1, head2);
        Node.printLinkedList(head);//0:0>1:1>4:4>5:5>6:6>8:8>10:10

    }


}
